\section{Теорема Кантора-Бернштейна}

\subsection*{44}

Очевидный контрпример квадраты чисел $A$ и $\mathbb{N}$. Очевидно $A \subsetneq \mathbb{N}$, но при этом $\exists \varphi: A \rightarrow N$, биективная - противоречие

\subsection*{45}

В качестве примера можно привести равномощность квадрата и круга.

Так как во всяком круге можно выделить квадрат, который очевидно равномощен всякому квадрату на плоскости. Так же как и во всяком квадрате можно выделить круг, который равномощен всякому кругу. Значит по теорме Кантора-Бернштейна всякий круг равномощен всякому квадрату

\subsection*{46}

Так как всякая фигура $\mathcal{F}_0$ содержащая хотя бы кусочек прямой равномощна $\mathbb{R}$, значит всякая такая фигура равномощна $\mathbb{R}^2$ - или же всей плоскости. При этом всякая другая фигура $\mathcal{F}$ является подмножеством $R^2$, значит является подмножеством $\mathcal{F}_0$. При этом, проведя аналогичные рассуждения $\mathcal{F}_0$ является подмножеством $\mathcal{F}$, значит по теореме Кантора-Бернштейна всякие фигуры на плоскости содержащие хотя бы кусочек прямой равномощны

\subsection*{47}

1) Пусть в одном из множеств есть отрезок

Тогда по теореме Кантора-Бернштейна оно равномощно исходному квадрату\\

2) Пусть в первом множестве нет отрезков

Тогда проведем прямые параллельные основанию квадрата. По условию в первом множестве нет сколь угодно малых отрезков, значит в каждой прямой есть хотя бы одна точка принадлежащаяя второму множеству

Так как можно провести $\mathbb{R}$ прямых параллельных основанию, то значит во втором множестве существует $\mathbb{R}$ подмножеств, в каждом из которых есть по крайней мере одна точка. По аксиоме выбора из каждого такого подмножества можно выбрать одну точку, составив подмножество из $\mathbb{R}$ элементов, которое очевидно будет равномощно исходному квадрату по теореме Кантора-Бернштейна

\subsection*{48}

1) Если одно из множеств содержит отрезок - очевидно\\

2) Если в первом множестве нет отрезков

Тогда сопоставим отрезку квадрат. Так как отезок и квадрат равномощны, значит существует биекция сопоставляющая кажой точке отрезка, точку квадрата. Тем самым первому множеству $A$ и второму множеству $B$ взаимно однозначно сопоставляются их образы в квадрате. Образы этих множеств назовем $A'$ и $B'$, тогда задача свелась к тому, чтобы доказать, что один из образов равномощен квадрату. По принципу чайника это так. Значит пусть $B'$ равномощно квадрату, и так как равномощность транзитивна, значит исходное $B$ так же равномощно квадрату, из чего следует, что $B$ равномощно отрезку

\subsection*{49}

$B_1 \subset B$; $A_2 \subset A_1 \subset A$; $f: A \rightarrow B_1$ - биекция; $g: B \rightarrow A_1$ - биекция\\

Так как $A$ равномощно $B_1$, значит каждому элементу из $A$ соответствует элемент из $B_1$. Поскольку $g: B \rightarrow A_1$, так как $B_1 \subset B$, по определению $f$ - переводит $B_1$ в $A_2: A_2 \subset A_1$, а так как $B_1$ равномощно $A_1$, значит $f: A \rightarrow A_2$\\

Введем новое определение, пусть $X \subset A$ - хорошее, если $X \supseteq (A \setminus A_1) \cup f(X)$\\

Легко видеть, что по крайней мере одно хорошее множество существует: так как $A \supseteq (A \setminus A_1) \cup f(A) = (A \setminus A_1) \cup A_2$, значит $A$ - хорошее.

Рассмотрим $M = \bigcap\limits_i X_i$, докажем, что оно хорошее.\\

Лемма: $X_i, X_j$ - хорошие, значит $X_i \cap X_j$ - хорошее

Рассмотрим $X_i \cap X_j:$

\begin{multline*}
X_i \cap X_j \supseteq ((A \setminus A_1) \cup f(X_i)) \cap ((A \setminus A_2) \cup f(X_j)) = \\
= (A \setminus A_1) \cup (f(X_i) \cap f(X_j)) =\\
= (A \setminus A_1) \cup f(X_i \cap X_j)
\end{multline*}

Значит $X_i \cap X_j$ - хорошее\\

Тогда из леммы очевидным образом следует, что $M = \bigcap\limits_i X_i$ - так же хорошее. Теперь покажем, что так как $M$ - минимальное по вложению хорошее множество, то знак подмножества из определения меняется на равенство\\

Так как $M$ - хорошее, значит $M \supseteq (A \setminus A_1) \cup f(M)$. Покажем что $(A \setminus A_1) \cup f(M)$ тоже хорошее:

Очевидно $A \setminus A_1 \subseteq (A \setminus A_1) \cup f(M)$,

\begin{multline*}
f([A \setminus A_1] \cup f(M)) \subseteq f(M) \subset [(A \setminus A_1) \cup f(M)]\\
\implies [(A \setminus A_1) \cup f(M)] \supseteq [(A \setminus A_1) \cup f(\{A \setminus A_1\} \cup f(M))]
\end{multline*}

Из чего следует, что $(A \setminus A_1) \cup f(M)$ - хорошее

Но так как $M$ - минимальное по вложению, значит $M = (A \setminus A_1) \cup f(M)$\\

Теперь рассмотрим функцию $m:$

\begin{equation*}
m(a) = 
    \begin{cases}
        f(a), & \text{при } a \in M\\
        id, & \text{при } a \notin M
    \end{cases}
\end{equation*}

Покажем что она задает биекцию между $A$ и $A_1$:

Очевидно $\forall x: x \notin M \implies x \in A_1$, так как $M = (A \setminus A_1) + f(M)$, значит $x \notin A \setminus A_1$, но так как $x \in A \implies x \in A_1$\\

Рассмотрим $x \in M$, тогда по определению $(x \in [A \setminus A_1]) \lor (x \in f(M))$

При $x \in A \setminus A_1 \implies f(x) \in A_1$ и $f(x) \in f(M)$

При $x \in f(M) \implies f(x) \in A_1$ и $f(x) \in f(f(M)) \subset f(M)$

И поскольку $m$ - взаимно однозначное (так как состоит из взаимно однозначных функций) отображение, мы каждому элементу $M$ однозначно сопоставили некоторый элемент $f(M) \subset A_1$

Следовательно так как мы поставили в соответствие всякому элементу $A$, элемент $A_1$, то $g^{-1} \circ m: A \rightarrow B$ - биекция

\subsection*{50}

Пусть $f$ - взаимно однозначное соответствие между $A$ и некоторым подмножеством $B$, а $g$ - взаимно однозначное соответствие между $B$ и некоторым подмножеством $A$

Доказать, что можно разбить множество $A$ на непересекающиеся подмножества $A'$ и $A''$, а множество $B$ на подмножества $B'$ и $B''$ так, чтобы $f: A' \rightarrow B'$, $g: B'' \rightarrow A''$\\

Построим функцию $H: X \rightarrow A \setminus g(B \setminus f(X))$, тогда $A' = H(A')$ будет исходным разбиением.

Назовем $X$ - хорошим, если $X \subseteq H(X)$\\

Лемма $X \subseteq Y \implies H(X) \subseteq H(Y)$

Доказательство следует из пошагового выполнения отображений функции $H$. Из $X \subseteq Y$ следует, что $f(X) \subseteq f(Y)$, из чего так же очевидно следует $B \setminus f(X) \supseteq B \setminus f(Y)$. Так же из $B \setminus f(X) \supseteq B \setminus f(Y)$ следует, что $f(B \setminus f(X)) \supseteq f(B \setminus f(Y))$, из чего немедленно следует $A \setminus f(B \setminus f(X)) \subseteq A \setminus f(B \setminus f(Y))$\\

Рассмотрим супер хорошее множество $Z = \bigcup\limits_i X_i$, покажем, что оно хорошее

\begin{multline*}
z \in Z \implies \exists X: z \in X \implies z \in H(X)\\
X \subseteq Z \implies H(X) \subseteq H(Z) \implies z \in H(Z)
\end{multline*}

И так как мы рассмотрели всякий элемент $z \implies Z \subseteq H(Z)$

Покажем, что $Z = H(Z)$, ad absurdum: Пусть $\exists z_0 \in H(Z) \setminus Z$, значит $\exists Z' = Z \cup \{z_0\}$

\begin{equation*}
\forall z \in Z' \implies
    \begin{cases}
        z \in Z \implies z \in H(Z) \implies z \in H(Z')\\
        z = z_0 \implies z \in H(Z')
    \end{cases}
\end{equation*}

Значит $Z'$ - хорошее и оно шире $Z$, но при этом $Z$ - объеденение всех хороших - противоречие. Значит $Z = H(Z)$

Тем самым мы построили разбиение $A' = Z$, теперь осталось построить биекцию между $A$ и $B$

\begin{equation*}
h(x) =
    \begin{cases}
        f(x), & \text{при } x \in A'\\
        g^{-1}(x), & \text{при } x \in A''
    \end{cases}
\end{equation*}

Тем самым мы построили биекцию между $A'$ и $B'$, и $A''$ и $B''$

\subsection*{51}

Так как во всякий квадрат $\mathcal{A}$ можно вписать круг, и во всяком кругу $\mathcal{B}$ можно выделить квадрат, и потому как всякий квадрат равномощен любому другому квадрату на плоскости, ровно как и всякий круг равномощен всякому другому кругу, значит существует $f: \mathcal{A} \rightarrow \mathcal{B'}$ - биекция, при $\mathcal{B'} \subset \mathcal{B}$ и $g: \mathcal{B} \rightarrow \mathcal{A'}$ - биекция, при $\mathcal{A'} \subset \mathcal{A}$. Из чего следует, что существуют $f: \mathcal{A'} \rightarrow \mathcal{B'}$ и $g: \mathcal{A''} \rightarrow \mathcal{B''}$

\subsection*{52}

Пусть несчетное множество $A$, а счетное множество $B$. Так как всякое несчетное множество содержит подмножество счетной мощности значит $\exists f: B \rightarrow A'$ - биекция, при $A' \subset A$. И так как множество несчетно, значит не существует $g: A \rightarrow B'$ - биекция, при $B' \subseteq B$, так как всякое подмножество счетного множества не более чем счетно. Тем самым несчетное множество строго больше счетного

\subsection*{53} 

Так как $\exists f: A \rightarrow B \implies A \sim fA \subset B$. И так как $B \leq C \implies \exists g: B \rightarrow C$, а поскольку $fA \subset B \implies g(fA) \subset gB \subset C$, при том, что $A \sim fA \sim g(fA) \implies \exists m: A \rightarrow C$, когда $m(x) = g(f(x)) \implies A \leq C$